Modern personal computer systems generally include one or more processors and a microprocessor cache memory system for each processor. A cache memory is a small amount of very fast, expensive, zero wait state memory which is used to store frequently used code and data. The cache system is the interface between the respective processor and the system bus and is used to bridge the gap between fast processor cycle times and relatively slow memory access times.
When a processor generates a read request and the requested data resides in its cache memory, then a cache read hit takes place, and the processor can obtain the data from the cache memory without having to access main memory. If the data is not in the cache memory, then a cache read miss occurs, and the memory request is forwarded to the system and the data is retrieved from the main memory, as would normally be done if the cache system did not exist. On a cache miss, the data that is retrieved from main memory is provided to the processor and is also written into the cache memory due to the statistical likelihood that this data will be requested again by the processor. Likewise, if a processor generates a write request, the write data can be written to the cache memory without having to access main memory over the system bus (in a write-back cache). This increases processor efficiency and reduces host bus utilization, allowing more bandwidth for other processors and bus masters.
An efficient cache system yields a high "hit rate," which is the percentage of cache hits that occur during all memory accesses. When a cache system has a high hit rate, the majority of memory accesses are serviced with zero wait states. Therefore, a processor operating out of its local cache memory has a much lower "bus utilization." This reduces system bus bandwidth used by the processor, making more bandwidth available for other bus masters. In addition, a processor can operate out of its local cache memory when it does not have control of the system bus, thereby increasing efficiency of the computer system.
Two principal types of cache systems are referred to as write-through cache systems and write-back cache systems. In write-through systems, write data from the processor is written into the cache and is also immediately written into main memory. This guarantees that the copy of data in the cache memory is coherent or consistent with the data in main memory. A drawback of write-through cache systems, however, is that host bus utilization is required for each processor write.
In a write-back cache system, processor write data is only written into the cache memory, and the write data is only written back to main memory when another device requests the data or it is cast out and replaced by a request for new data. When processor write data is written only into the cache system, the data held in the corresponding location in main memory is referred as stale or invalid data. The cache location is said to hold modified data. In write-back cache systems, the cache controller is required to watch or "snoop" the system bus during cycles by other bus masters, e.g., processors, as described below.
Cache management is generally performed by a device referred to as a cache controller. A principal cache management policy is the preservation of cache coherency. Cache coherency refers to the requirement that any bus device requesting data receives the most recent version of the data. The owner of a location's data is generally defined as the respective location having the most recent version of the data residing in the respective memory location. The owner of data can be either an unmodified location in main memory, or a modified location in a write-back cache.
In computer systems where independent bus masters can access main memory, there is a possibility that a bus master, such as another processor, or a direct memory access controller, network or disk interface card, or video graphics card, might alter the contents of a main memory location that is duplicated in the cache memory. When this occurs, the cache memory is said to hold "stale" or invalid data. Problems would result if the processor inadvertently obtained this invalid data. In order to maintain cache coherency, therefore, it is necessary for the cache controller to monitor the system bus when the processor does not control the bus to see if another bus master accesses main memory. This method of monitoring the bus is referred to in the art as "snooping."
The cache controller must also monitor the system bus during main memory reads by a bus master in a write-back cache design because of the possibility that a previous processor write may have altered a copy of data in the cache memory that has not been updated in main memory. This is referred to as read snooping. On a read snoop hit where the cache memory contains data not yet updated in main memory, the cache controller generally provides the respective data to main memory and to the requesting bus master.
The cache controller must also monitor the system bus during memory writes because the bus master may write to or alter a memory location that resides in its cache memory. This is referred to as write snooping. On a write snoop hit, the cache entry is either marked invalid in the cache controller, signifying that this entry is no longer correct, or the cache memory is updated along with the main memory.
Therefore, when a bus master reads or writes to main memory in a write-back cache design, or writes to main memory in a write-through cache design, the cache controller must latch the system address and see if the main memory location being accessed also resides in the cache memory. If a copy of the data from this location does reside in the cache memory, then the cache controller takes the appropriate action depending upon whether a read or write snoop hit has occurred. This prevents stale data from being stored in main memory and the cache memory, thereby preserving cache coherency.
The problem of inconsistency or cache incoherence can occur for any one of multiple reasons; for example, as a result of sharing of writable data, from process migration, or from input/output (I/O) activity. A number of methods have been proposed/implemented for handling coherency of memory or data. For example, reference U.S. Pat. Nos. 5,025,365; 5,249,283; and 5,353,415.
One simple solution to the cache coherency problem is to require main memory to record the location of each encached copy of data associated with a main memory address. When any encached copy is modified, the results are automatically stored in the cache of the processor performing the processing, copied through to the corresponding address in main memory, and then copied to each additional cache that also has data associated with the main address. This copy back process works quite well for two processor systems; however, as the number of processors increases, the interconnect sub-system tends to become overloaded by frequent copying back of information to main memory and the frequent updating of all encached copies of the information. In such a system, the gains in processor power provided by multiple processors may be negated by the overloading of the system interconnect by update messages to the processor caches.
Another method is to use open-collector signals for the address/snoop response. This allows multiple bus masters to drive signals concurrently, while only requiring the use of three signal lines, that is, a shared signal line, a modified signal line, and a retry signal line. The disadvantage is that the minimum turnaround time for the address bus is four clock cycles, i.e., if signals are changing with respect to the same clock edge (rising or falling). The minimum turnaround time for the address bus can be reduced to three clock cycles if the signals are allowed to change with respect to both the rising and falling clock edge. However, this complicates the control logic for the address/snoop response signals, which is usually one of the critical path signals.
Thus, a need continues to exist for an improved method and system for handling cache coherency in multiple bus master systems, such as multiprocessor systems, and more particularly, for an approach which avoids excessive delay in either address bus turnaround time or snoop response time. The present invention addresses this need.